//双向链表
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define TYPE int 

typedef struct Node
{
	struct Node* prev;//前一个元素
	TYPE data;
	struct Node* next;//后一个元素
}Node;

Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->prev=NULL;
	node->data=data;
	node->next=NULL;
	return node;
}

typedef struct List
{
	Node* head;
	Node* tail;
	size_t size;
}List;

//创建
List* creat_list(void);
//销毁
void destory_list(List* list);
//头加
void head_add_list(List* list,TYPE data);
//尾加
void tail_add_list(List* list,TYPE data);
//插入
bool insert_list(List* list,int index,TYPE data);
//位置删除
bool delete_index_list(List* list,int index);
//值删除
bool delete_value_list(List* list,TYPE data);
//遍历
void show_list(List* list);
//头删除
bool del_head_list(List* list)
{
	if(list->size<=0) return false;
	Node* node = list->head;
	if(1 == list->size)
	{
		list->head = NULL;
		list->tail = NULL;
	}
	else
	{
		list->head=node->next;
		node->next->prev =NULL;	
	}
	free(node);
	list->size--;
	return true;
}

//尾删除
bool del_tail_list(List* list)
{
	if(list->size<=0 )return false;
	Node* node=list->tail;
	if(1 == list->size)
	{
		list->head=NULL;
		list->tail=NULL;
	}
	else
	{
		list ->tail=node->prev;
		node->prev->next = NULL;
	}
	free(node);
	list->size--;
	return true;

}

int main()
{
	List* list = creat_list();
	for(int i=0 ;i<10;i++)
	{
		head_add_list(list,i);	
	}
	show_list(list);
	printf("=============\n");
//	insert_list(list,9,4);
	delete_value_list(list,0);
	show_list(list);
}

//创建
List* creat_list(void)
{
	List* list = malloc(sizeof(List));
	list->head = NULL;
	list->tail = NULL;
	list->size = 0;
	return list;
}
//销毁
void destory_list(List* list)
{
	
	free(list);	
}
//头加
void head_add_list(List* list,TYPE data)
{
	Node* node =creat_node(data);
	if(0==list->size)
	{
		list->head=node;
		list->tail=node;
	}
	else
	{
		node->next = list ->head;
		list->head->prev = node;
		list->head = node;
	}

	list->size++;
}
//尾加
void tail_add_list(List* list,TYPE data)
{
	Node* node = creat_node(data);
	if(0==list->size)
	{
		list->head=node;
		list->tail=node;
	}
	else
	{
		list->tail->next = node;
		node->prev=list->tail;
		list->tail=node;
	}
	list->size++;
}
//插入
bool insert_list(List* list,int index,TYPE data)
{
	if(index < 0 || index>=list->size) return false;
	if(index==0)
	{
		head_add_list(list,data);
		return true;
	} 
	if(index==list->size-1)
	{
		tail_add_list(list,data);
		return true;
	} 
	Node* p=list->head;
	for(int i=0;i<index-1;i++)
		p=p->next;

	Node* node = creat_node(data);
	p->next->prev = node;
	node->next = p->next;
	p->next = node;
	node->prev = p;
	list->size++;
	return true;
	
}
//位置删除
bool delete_index_list(List* list,int index)
{
	if(index<0||index>=list->size) return false;
	if(index==0)
	{
		Node* node = list->head;	
		list->head = node->next;
		node->next->prev=NULL;
	if(1 == list ->size)
	{
		list->tail = NULL;
	}
	free(node);
	list->size--;
	return true;
	}
	if(index==list->size-1)
	{
		Node* p=list->head;
		while( p->next!=list->tail)
		{
			p=p->next;
		}
		p->prev=list->tail->prev;
		free(list->tail);
		list->tail=p;
		p->next=NULL;
		list->size--;
		return true;
	}
	else
	{
		Node* p=list->head;
		for(int i=0;i<index-1;i++)
		{
			p = p->next;
		}
		Node* node = p->next;
		p->next = node->next;
		node->next->prev=p;
		free(node);
		list->size--;
	}

		return true;
	
}
//值删除
bool delete_value_list(List* list,TYPE data)
{	
	if(data==list->head->data)	
		return	del_head_list(list);	
	if(data==list->tail->data)	
		return	del_tail_list(list);	


	Node* node =list->head;
	while(NULL!=node)
	{
		if(data==node->data) break;
			node=node->next;	
	}

	Node* prev = node->prev;
	Node* next = node->next;
	prev->next = next;
	next->prev = prev;
	free(prev);    
	list->size--;
	return false;
}

//遍历
void show_list(List* list)
{
	for(Node* i=list->head;i!=NULL;i=i->next)
	{
		printf("%d ",i->data);	
	}
	printf("\n-------------------\n");
	for(Node* i=list->tail;i!=NULL;i=i->prev)
	{
		printf("%d ",i->data);	
	}
	printf("\n");


}


